/**
 * 98. 验证二叉搜索树
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 */
const { createTreeNode } = require('../../libs/public');

// /**
//  * @param {TreeNode} node
//  * @return {{ min?: number, max?: number }|boolean}
//  */
// function validate(node) {
//   const msg = { min: node.val, max: node.val };
//   if (node.left) {
//     const result = validate(node.left);
//     if (result === false) return false;
//     if (result.max >= node.val) return false;
//     msg.min = result.min;
//   }
//   if (node.right) {
//     const result = validate(node.right);
//     if (result === false) return false;
//     if (result.min <= node.val) return false;
//     msg.max = result.max;
//   }
//   return msg;
// }
//
// /**
//  * @param {TreeNode} root
//  * @return {boolean}
//  */
// function isValidBST(root) {
//   return !!validate(root);
// }

// /**
//  * @param {TreeNode} node
//  * @param {number} min
//  * @param {number} max
//  * @return {boolean}
//  */
// function recursion(node, min, max) {
//   if (!node) return true;
//   if (node.val <= min || node.val >= max) return false;
//   if (!recursion(node.left, min, node.val)) return false;
//   if (!recursion(node.right, node.val, max)) return false;
//   return true;
// }
//
// /**
//  * 递归
//  * @param {TreeNode} root
//  * @return {boolean}
//  */
// function isValidBST(root) {
//   return recursion(root, -Infinity, Infinity);
// }

/**
 * 中序遍历
 * @param {TreeNode} root
 * @return {boolean}
 */
function isValidBST(root) {
  const stack = [];
  let node = root;
  let last = -Infinity;
  while (node || stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    if (node.val <= last) return false;
    last = node.val;
    node = node.right;
  }
  return true;
}

console.log(isValidBST(createTreeNode([2, 1, 3])) === true);
console.log(isValidBST(createTreeNode([5, 1, 4, null, null, 3, 6])) === false);
// console.log(JSON.stringify(createTreeNode([5, 4, 6, null, null, 3, 7]), null, 2));
console.log(isValidBST(createTreeNode([5, 4, 6, null, null, 3, 7])) === false);
